package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

//Suppose you have a random list of people standing in a queue. 
//Each person is described by a pair of integers (h, k), where h is the height of the person and k is the 
//number of people in front of this person who have a height greater than or equal to h. 
//Write an algorithm to reconstruct the queue.

//Input:
//[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
//
//Output:
//[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
public class QueueReconstructionByHeight {

	//We first sort the people to make them stand from the highest to shortest. 
	//For people with same height, sort them according to the count of people before them from small to big.
    public int[][] reconstructQueue(int[][] people) {
    	if (people == null || people.length == 0 || people[0].length == 0){
            return new int[0][0];
    	}
    	Arrays.sort(people, new Comparator<int[]>() {
    		@Override
    		public int compare(int[] arr1, int[] arr2) {
    			if(arr1[0] == arr2[0]){
    				//small to big
    				return arr1[1] - arr2[1];
    			}
    			//highest to shortest
    			return arr2[0] - arr1[0];
    		}
		});
    	int length = people.length;
    	//插入排序的过程
    	//Then, we use the way similar to insert sorting to reorder the people. For a given person to insert, 
    	//all the people already sorted are higher, so we just insert him in the "right" place to make the
    	//people before him as his "count" indicates.(刚好插入到他的count所在的下标处) 
    	//Since he is shorter than all the people in the sorted list, 
    	//the "count" of the "existing" people does not be broken by the insertion.
    	//(因为是从左往右，按照高度从高往低进行的插入排序，所以小的插在大的不会影响其他的count)
    	//比如[7,0] [7,1], [6,1], [5, 1]
    	//[5, 1]插在下标1的位置，不会影响6和7
    	ArrayList<int[]> list = new ArrayList<>();
    	for (int i = 0; i < length; i++) {
    		//people[i][1]是该人前面有几个大于等于的值
    		//此时people已经是排过序的了
    		//所以会将people[i][1]相等时high小的放在前面
			list.add(people[i][1], new int[]{people[i][0], people[i][1]});
		}
    	
    	int[][] res = new int[length][2];
    	int index = 0;
    	for (int[] k : list) {
			res[index][0] = k[0];
			res[index][1] = k[1];
			index++;
		}
    	return res;
    }
}
